This relates to the field of graphics processing.
Collision detection (CD) is used in games and other applications to handle interaction between objects. CD algorithms can be broadly divided into discrete and continuous methods. Discrete methods only detect if two objects collide at a specific (discrete) point in time. Events falling between such discrete times cannot be detected, which in some cases could be a severe limitation. For example, a fast object (e.g. a ball) moving towards a wall might experience a “tunneling” effect if it is in front of the wall at one inspected point in time (frame) and behind the wall at the next point in time. Continuous CD (CCD) algorithms on the other hand, avoid these problems by instead computing the time of the first contact between two objects. This is crucial for realistic animations, but also more expensive in terms of the necessary amount of computations.
A brute force technique to detect collision considers all moving triangles in a scene and compares them to all other triangles. A computationally relatively expensive triangle-triangle intersection test is performed between all pairs of triangles. With many objects, this technique becomes intractable. Therefore, different approaches to culling are taken, whereby (preferably large groups of) triangles are conservatively excluded from testing at an early stage. For instance, a rigid object can never collide with itself and its triangles can thus be excluded from testing against any other triangle in that object. Also, if the bounding box of one static object does not overlap with the bounding box of another static object, then these two objects do not need further collision detection, since they clearly will not collide.
Another such culling technique, N. K. Govindaraju, S. Redon, M. C. Lin, and D. Manocha, “CULLIDE: Interactive Collision Detection between Complex Models in Large Environments using Graphics Hardware”, Graphics Hardware, pp. 25-32, 2003, utilizes occlusion queries (OQ) to create an ordering between objects in the scene. In short, a pair of objects belongs to a Potentially Colliding Set (PCS) if it cannot be conservatively established that the objects are not colliding at a discrete point in time. For each frame, the PCS is created by repeatedly performing an OQ for all axes (x, y, and z) and directions (positive, negative) for all objects. During this process, objects are removed from the PCS as it is detected that they do not collide. Detailed triangle-triangle intersection tests need only be performed between objects in the PCS.
However, an important drawback of the basic PCS culling technique is that it only handles discrete detection, i.e., if objects are moving too fast, the technique could potentially fail to detect collisions during a certain period of time.